//线段树
#include <bits/stdc++.h>
using namespace std;
void pushdown(int x)
{
	cov[cur<<1]+=cov[cur];
	cov[cur<<1|1]+=cov[cur];//乘二加一,标记当前节点左儿子右儿子
	sum[cur<<1]+=cov[cur]*(x+1>>1);
	sum[cur<<1|1]+=cov[cur]*(x>>1);//修改左、右儿子的
	cov[cur]=0;
}
void update(int cur)
{
	sum[cur]=sum[cur<<1]+sum[cur<<1|1]
}
//修改
void add(int l,int r,int L,int R,int x,int cur)//给LR加权值
{
	if(L<=l&&R>=r)//包含
	{
		cov[cur]+=x;
		sum[cur]+=(r-l+1)*x;
		return;
	}
	if(cov[cur])	pushdown(cur);
	int mid=l+r>>1;
	if(L<=mid)
		add(l,mid,L,R,x,cur<<1);
    if(R>mid)
    	add(mid+1,r,L,R,x,cur<<1|1);
    update(cur);
}
int query(int l,int r,int L,int R,int cur)
{
	if(L<=l&&R>=r)
		return sum[cur];
	if(cov[cur])
		pushdown(cur,r-l+1);
	int mid=l+r>>1,ans=0;
	if(L<=mid)
		ans+=query(l,mid,L,R,cur<<1);
	if(R>mid)
		ans+=query(mid+1,r,L,R,cur<<1|1)
	return ans;

}
